package Other;

public class leet_62 {
    public static void main(String[] args) {
        Solution_62 p =new Solution_62();
        int value = p.uniquePaths(3, 3);
        System.out.println(value);
    }

}


class Solution_62 {
    public int uniquePaths(int m, int n) {
        // 初始化数组
        int[][] dp =new int[m][n];
        // 向左一直走
        for(int i=0; i<m; i++){
            dp[i][0] = 1;
        }
        // 向下一直走
        for(int j=0; j<n; j++){
            dp[0][j] = 1;
        }
        // 从左到右 一层层的遍历
        for(int j=1; j<n; j++){
            for(int i=1; i<m; i++){
                //  [i-1][j] 从左边过来
                //  [i][j-1] 从上面过来
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
